//B树
#ifndef __BTREE__HPP
#define __BTREE__HPP

#include"../Universal.h"
#include"../../Algorithm/Sort.hpp"

namespace NgSiuKei {

template<class TheClass>
struct b_tree_node {
    U_L_L m;
    b_tree_node<TheClass> *parent;
    U_L_L valNum;
    TheClass *vals;
    b_tree_node<TheClass> **childs;
    b_tree_node<TheClass> *nextOne;//只用B+树和B*树会用到
};

//判断节点是否富裕
//“富裕”这个概念时间旧了容易忘，解释了啥是“贫瘠”就能理解啥是“富裕”
//“贫瘠”就是两个“贫瘠”节点合并在一起都不会超出价数m为之“贫瘠”
static bool isRich(U_L_L num, U_L_L m) {
    if(0 == num) {
        return false;
    }
    return num >= ((m+((0!=m%2)?(1):(0)))/2)-1;
}

//取最小值
template<class TheClass>
static TheClass getMinVal(b_tree_node<TheClass> *tree) {
    if(nullptr == tree) {
        throw EXCEPTION_CAN_NOT_FIND;
    }
    if(nullptr != tree->childs[0]) {
        return getMinVal(tree->childs[0]);
    }
    return tree->vals[0];
}
template<class TheClass>
static TheClass getMinVal(b_tree_node<TheClass> *tree, b_tree_node<TheClass> *&outputNode) {
    if(nullptr == tree) {
        throw EXCEPTION_CAN_NOT_FIND;
    }
    if(nullptr != tree->childs[0]) {
        return getMinVal(tree->childs[0], outputNode);
    }
    outputNode = tree;
    return tree->vals[0];
}

//获取叶节点数量
template<class TheClass>
static U_L_L getLeafNodeNum(b_tree_node<TheClass> *&tree) {
    if(nullptr == tree || nullptr == tree->childs) {
        return 0;
    }
    if(nullptr == tree->childs[0]) {
        return 1;
    }
    U_L_L num = 0;
    for(U_L_L i=0; i<=tree->valNum; ++i) {
        num += getLeafNodeNum(tree->childs[i]);
    }
    return num;
}

//获取所有叶节点
template<class TheClass>
static b_tree_node<TheClass> **getAllLeafNode(b_tree_node<TheClass> *&tree) {
    U_L_L num = getLeafNodeNum(tree);
    b_tree_node<TheClass> **leafNodes = new b_tree_node<TheClass> *[num];
    U_L_L index = 0;
    getAllLeafNodeIntoArray(tree, leafNodes, index);
    return leafNodes;
}
template<class TheClass>
static void getAllLeafNodeIntoArray(b_tree_node<TheClass> *&tree, b_tree_node<TheClass> **&array, U_L_L &index) {
    if(nullptr == tree || nullptr == array) {
        return;
    }
    if(nullptr == tree->childs[0]) {
        array[index++] = tree;
        return;
    }
    for(U_L_L i=0; i<=tree->valNum; ++i) {
        getAllLeafNodeIntoArray(tree->childs[i], array, index);
    }
}

//设置所有子节点的父节点属性
template<class TheClass>
static void setAllNodeParent(b_tree_node<TheClass> *&tree, b_tree_node<TheClass> *parent = nullptr) {
    // return;
    if(nullptr == tree) {
        return;
    }

    // //-----------------------------------------------------------------
    // debugOut << "改变前-> [ ";
    // if(nullptr == parent) {
    //     cout << 0;
    // }
    // else {
    //     for(U_L_L i=0; i<parent->valNum; ++i) {
    //         cout << parent->vals[i] << ' ';
    //     }
    // }
    // cout << " ] -> [ ";
    // for(U_L_L i=0; i<tree->valNum; ++i) {
    //     cout << tree->vals[i] << ' ';
    // }
    // cout << ']' << endl;

    // /////////////////////////
    tree->parent = parent;
    // /////////////////////////
    
    // debugOut << "改变后-> [ ";
    // if(nullptr == parent) {
    //     cout << 0 << ' ';
    // }
    // else {
    //     for(U_L_L i=0; i<parent->valNum; ++i) {
    //         cout << parent->vals[i] << ' ';
    //     }
    // }
    // cout << "] -> [ ";
    // for(U_L_L i=0; i<tree->valNum; ++i) {
    //     cout << tree->vals[i] << ' ';
    // }
    // cout << ']' << endl;
    // //-----------------------------------------------------------------
    
    if(nullptr != tree->childs) {
        for(U_L_L i=0; i<=tree->valNum; ++i) {
            setAllNodeParent(tree->childs[i], tree);
        }
    }
}

//创建节点
template<class TheClass>
static b_tree_node<TheClass> *cerateBTreeNode(TheClass val, const U_L_L m, b_tree_node<TheClass> *parent = nullptr) {
    if(m < 3) {
        return nullptr;
    }

    b_tree_node<TheClass> *tree = new b_tree_node<TheClass>;
    tree->m = m;
    tree->parent = parent;
    tree->valNum = 1;
    tree->vals = new TheClass[m];
    tree->vals[0] = val;
    tree->childs = new b_tree_node<TheClass>*[m+1];
    for(U_L_L i=0; i<m+1; ++i) {
        tree->childs[i] = nullptr;
    }
    tree->nextOne = nullptr;

    return tree;
}

//删除树
template<class TheClass>
void deleteBTree(b_tree_node<TheClass> *&tree, bool needDeleteChild = true) {
    if(nullptr == tree) {
        return;
    }

    if(nullptr != tree->childs && needDeleteChild) {
        for(U_L_L i=0; i<tree->valNum+1; ++i) {
            deleteBTree(tree->childs[i]);
        }
    }

    if(nullptr != tree->vals) {
        delete []tree->vals;
        tree->vals = nullptr;
    }
    if(nullptr != tree->childs) {
        delete []tree->childs;
        tree->childs = nullptr;
    }
    tree->parent = nullptr;
    tree->nextOne = nullptr;
    delete tree;
    tree = nullptr;
}

//拆分树节点
template<class TheClass>
static void resolveBTreeNode(b_tree_node<TheClass> *&tree) {
    if(nullptr == tree) {
        return;
    }

    U_L_L i;
    U_L_L index = (tree->m-((0==tree->m%2)?(1):(0)))/2;//中间节点下标

    //中间值
    TheClass centerVal = tree->vals[index];

    //创建拆分后的大一点的新节点
    U_L_L biggerNodeValsNum = tree->m-index-1;
    TheClass *dataBigger = new TheClass[biggerNodeValsNum];
    for(i=0; i<biggerNodeValsNum; ++i) {
        dataBigger[i] = tree->vals[index+i+1];
    }
    b_tree_node<TheClass> *biggerNode = cerateBTreeNode(dataBigger[0], tree->m);
    biggerNode->valNum = biggerNodeValsNum;
    for(i=1; i<biggerNodeValsNum; ++i) {
        biggerNode->vals[i] = dataBigger[i];
    }
    if(nullptr != tree->childs[0]) {
        for(i=0; i<=biggerNodeValsNum; ++i) {
            biggerNode->childs[i] = tree->childs[index+i+1];
            tree->childs[index+i+1] = nullptr;
        }
    }
    // cout << "biggerNode = " << biggerNode << endl;
    // printBTree(biggerNode);

    //tree变成小一点的那个节点，删除数值、子树
    for(i=0; i<tree->valNum-index; ++i) {
        tree->childs[i+index+1] = nullptr;
    }
    tree->valNum = index;//数据数量变小就相当于删除数据
    // cout << "tree = " << tree << endl;
    // printBTree(tree);

    if(nullptr == tree->parent) {
        //被拆分的是根节点，需要创建新的根节点
        b_tree_node<TheClass> *newRootNode = cerateBTreeNode(centerVal, tree->m);

        //父节点塞入新节点，新节点引用父节点
        newRootNode->childs[0] = tree;
        newRootNode->childs[1] = biggerNode;
        tree->parent = newRootNode;
        biggerNode->parent = newRootNode;

        // cout << "newRootNode = " << newRootNode << endl;
        // printBTree(newRootNode);

        //tree指向新根节点
        tree = newRootNode;

        //重新设置所有节点父属性
        setAllNodeParent(tree);

        // cout << "newTree = " << tree << endl;
        // printBTree(tree);
    }
    else {
        // cout << "==========打印父节点信息==========" << endl;
        // cout << tree->parent << endl;
        // cout << tree->parent->m << endl;
        // cout << tree->parent->valNum << endl;
        // cout << tree->parent->vals[0] << endl;
        // cout << tree->parent->childs[0] << endl;
        // cout << tree->parent->parent << endl;
        // cout << "================================" << endl;

        //定位中间值应该塞入的位置
        U_L_L centerValIndex = 0;
        for(i=0; i<tree->parent->valNum; ++i) {
            if(centerVal < tree->parent->vals[i]) {
                centerValIndex = i;
                break;
            }
            else if(tree->parent->valNum-1 == i) {
                centerValIndex = tree->parent->valNum;
                break;
            }
        }

        //父节点值后移
        for(i=tree->parent->valNum; i>centerValIndex; --i) {
            tree->parent->vals[i] = tree->parent->vals[i-1];
        }
        //父节点子树后移
        for(i=tree->parent->valNum+1; i>centerValIndex+1; --i) {
            tree->parent->childs[i] = tree->parent->childs[i-1];
        }

        //父节点塞入中间值
        tree->parent->vals[centerValIndex] = centerVal;
        tree->parent->valNum++;

        //父节点塞入新节点，新节点引用父节点
        tree->parent->childs[centerValIndex+1] = biggerNode;
        biggerNode->parent = tree->parent;

        //重新设置所有节点父属性
        setAllNodeParent(tree->parent, tree->parent->parent);

        //若父节点被添加中间值后满了了，就拆分父节点
        if(tree->parent->m == tree->parent->valNum) {
            resolveBTreeNode(tree->parent);
        }
    }

    delete []dataBigger;
}

//查找
template<class TheClass>
bool findValInBTree(b_tree_node<TheClass> *&tree, TheClass val) {
    if(nullptr == tree) {
        return false;
    }
    bool result = false;
    for(U_L_L i=0; i<tree->valNum; ++i) {
        if(val == tree->vals[i]) {
            return true;
        }
        else if(val < tree->vals[i]) {
            result = result || findValInBTree(tree->childs[i], val);
        }
        else if(i == tree->valNum-1) {
            result = result || findValInBTree(tree->childs[tree->valNum], val);
        }
    }
    return result;
}

//插入值
template<class TheClass>
void insertValIntoBTree(b_tree_node<TheClass> *&tree, TheClass val) {
    if(nullptr == tree) {
        return;
    }

    if(nullptr == tree->childs[0]) {
        //叶子结点
        tree->vals[tree->valNum] = val;
        tree->valNum++;
        bubbleSort(tree->vals, tree->valNum);

        if(tree->m == tree->valNum) {
            //满了，需要拆分节点
            resolveBTreeNode(tree);
        }
    }
    else {
        //非叶子节点，爬树
        for(U_L_L i=0; i<tree->valNum; ++i) {
            if(val == tree->vals[i]) {
                //值已存在
                break;
            }
            else if(val < tree->vals[i]) {
                insertValIntoBTree(tree->childs[i], val);
                break;
            }
            else if(i == tree->valNum-1) {
                insertValIntoBTree(tree->childs[tree->valNum], val);
                break;
            }
        }
    }
}

//删除值
template<class TheClass>
void deleteValFromBTree(b_tree_node<TheClass> *&tree, TheClass val) {
    if(nullptr == tree || !findValInBTree(tree, val)) {
        return;
    }

    U_L_L j, k;
    for(U_L_L i=0; i<tree->valNum; ++i) {
        if(val < tree->vals[i]) {
            deleteValFromBTree(tree->childs[i], val);
            break;
        }
        else if(val == tree->vals[i]) {
            //删除操作
            //非叶节点，将值与右孩子最小值替换，再执行删除操作
            if(nullptr != tree->childs[0]) {
                b_tree_node<TheClass> *minNode = nullptr;
                TheClass minVal = getMinVal(tree->childs[i+1], minNode);
                minNode->vals[0] = val;
                tree->vals[i] = minVal;
                deleteValFromBTree(tree->childs[i+1], val);
                break;
            }

            //直接删
            --tree->valNum;
            for(j=i; j<tree->valNum; ++j) {
                tree->vals[j] = tree->vals[j+1];
            }
            break;
        }
        else if(i == tree->valNum-1) {
            deleteValFromBTree(tree->childs[tree->valNum], val);
            break;
        }
    }

    //重新设置所有节点父属性
    setAllNodeParent(tree, tree->parent);

    //经过删除操作后，自身可能变得不富裕，这时候要做特殊处理
    if(!isRich(tree->valNum, tree->m) && nullptr != tree->parent) {//找富兄弟拿，没有富兄弟就拿老爸的（注意子节点的移动）
        //寻找自己在父亲的子节点列表的下标
        for(j=0; j<=tree->parent->valNum; ++j) {
            if(tree->parent->childs[j] == tree) {
                break;
            }
        }
        if(j == tree->parent->valNum+1) {
            debugOut << endl;
            throw EXCEPTION_CAN_NOT_FIND;
        }
        //寻找可以拿值的富裕兄弟
        bool haveRichBrother = false;
        b_tree_node<TheClass> *leftBrother = nullptr;
        b_tree_node<TheClass> *rightBrother = nullptr;
        if(j > 0) {
            leftBrother = tree->parent->childs[j-1];
        }
        if(j < tree->parent->valNum) {
            rightBrother = tree->parent->childs[j+1];
        }
        if(nullptr != leftBrother && isRich(leftBrother->valNum-1, leftBrother->m)) {
            rightBrother = tree;
            haveRichBrother = true;
        }
        if(!haveRichBrother && nullptr != rightBrother && isRich(rightBrother->valNum-1, rightBrother->m)) {
            leftBrother  = tree;
            haveRichBrother = true;
        }
        //找富兄弟拿，没有富兄弟就拿老爸的（注意子节点的移动）
        if(haveRichBrother) {
            if(leftBrother == tree) {//右兄弟有钱
                //拿父节点值
                leftBrother->vals[leftBrother->valNum] = tree->parent->vals[j];
                ++leftBrother->valNum;
                //拿右兄弟最小子节点
                leftBrother->childs[leftBrother->valNum] = rightBrother->childs[0];
                //父节点拿右兄弟值
                tree->parent->vals[j] = rightBrother->vals[0];
                --rightBrother->valNum;
                //右兄弟值左移
                for(k=0; k<rightBrother->valNum; ++k) {
                    rightBrother->vals[k] = rightBrother->vals[k+1];
                }
                //右兄弟子节点左移
                for(k=0; k<=rightBrother->valNum; ++k) {
                    rightBrother->childs[k] = rightBrother->childs[k+1];
                }
                rightBrother->childs[rightBrother->valNum+1] = nullptr;
            }
            else {//左兄弟有钱
                //值右移
                for(k=rightBrother->valNum; k>0; --k) {
                    rightBrother->vals[k] = rightBrother->vals[k-1];
                }
                //子节点右移
                for(k=rightBrother->valNum+1; k>0; --k) {
                    rightBrother->childs[k] = rightBrother->childs[k-1];
                }
                //拿父节点值
                rightBrother->vals[0] = tree->parent->vals[j-1];
                ++rightBrother->valNum;
                //拿左兄弟最大子节点
                rightBrother->childs[0] = leftBrother->childs[leftBrother->valNum];
                leftBrother->childs[leftBrother->valNum] = nullptr;
                //父节点拿左兄弟值
                --leftBrother->valNum;
                tree->parent->vals[j-1] = leftBrother->vals[leftBrother->valNum];
            }
        }
        else {
            //默认和右兄弟合并，除非没有右兄弟
            U_L_L parentValIndex = j;
            if(nullptr != rightBrother) {
                leftBrother = tree;
            }
            else {
                parentValIndex = j-1;
                rightBrother = tree;
            }
            //leftBrother和rightBrother已经分别保存了兄弟节点和自己节点，后面的操作全部合并到leftBrother上，抛弃rightBrother
            //获取父节点值
            leftBrother->vals[leftBrother->valNum] = tree->parent->vals[parentValIndex];
            ++leftBrother->valNum;
            //获取右节点值
            for(k=0; k<rightBrother->valNum; ++k) {
                leftBrother->vals[leftBrother->valNum+k] = rightBrother->vals[k];
            }
            //获取右节点孩子
            for(k=0; k<=rightBrother->valNum; ++k) {
                leftBrother->childs[leftBrother->valNum+k] = rightBrother->childs[k];
            }
            leftBrother->valNum += rightBrother->valNum;
            //抛弃右兄弟
            deleteBTree(rightBrother, false);
            //父节点调整数组
            --leftBrother->parent->valNum;
            for(k=parentValIndex; k<leftBrother->parent->valNum; ++k) {
                leftBrother->parent->vals[k] = leftBrother->parent->vals[k+1];
            }
            for(k=parentValIndex; k<=leftBrother->parent->valNum; ++k) {
                leftBrother->parent->childs[k] = leftBrother->parent->childs[k+1];
            }
            leftBrother->parent->childs[parentValIndex] = leftBrother;
            tree = leftBrother;
            //如果合并节点之后太富裕了，需要拆分节点（理论上没有这个情况）
            if(tree->valNum == tree->m) {
                resolveBTreeNode(tree);
            }
        }
    }
    if(0 == tree->valNum) {
        b_tree_node<TheClass> *nullNode = tree;
        tree = tree->childs[0];
        tree->parent = nullNode->parent;
        deleteBTree(nullNode, false);
    }

    return;
}

//创建
template<class TheClass>
b_tree_node<TheClass> *createBTree(TheClass *data, U_L_L dataSize, const U_L_L m) {
    if(nullptr == data && m < 3) {
        return nullptr;
    }

    b_tree_node<TheClass> *tree = cerateBTreeNode(data[0], m);
    for(U_L_L i=1; i<dataSize; ++i) {
        insertValIntoBTree(tree, data[i]);
        while(nullptr != tree->parent) {
            tree = tree->parent;
        }
    }

    // while(nullptr != tree->parent) {
    //     tree = tree->parent;
    // }

    // cout << "[From Create]-[" << tree << ']' << endl;
    return tree;
}

//打印
template<class TheClass>
void printBTree(b_tree_node<TheClass> *tree) {
    if(nullptr == tree) {
        cout << "null." << endl;
        return;
    }
    if(nullptr == tree->parent) {
        cout << "[root]-";
    }
    cout << "[" << tree << "]-[" << tree->valNum << "]-[ ";
    for(U_L_L i=0; i<tree->valNum; ++i) {
        cout << tree->vals[i] << ' ';
    }
    cout << ']' << endl;

    if(nullptr != tree->childs) {
        for(U_L_L i=0; i<tree->valNum+1; ++i) {
            if(nullptr != tree->childs[i]) {
                if(i == 0) {
                    cout << "["<< tree->valNum << "]" << "[L" << tree->vals[0] << "]-";
                }
                else if(i == tree->valNum) {
                    cout << "["<< tree->valNum << "]" << "[R" << tree->vals[tree->valNum-1] << "]-";
                }
                else {
                    cout << "["<< tree->valNum << "]" << "[" << tree->vals[i-1] << '-' << tree->vals[i] << "]-";
                }
                printBTree(tree->childs[i]);
            }
        }
    }
}

}

#endif